//class Solution {
//public:
//
//    int lengthOfLIS(vector<int>& nums) {
//        int ret = 0, n = nums.size();
//        vector<int> memo(n);
//        for (int i = 0; i < n; i++)
//            ret = max(ret, dfs(nums, memo, i));
//        return ret;
//    }
//
//    int dfs(vector<int>& nums, vector<int>& memo, int pos)
//    {
//
//        int ans = 0;
//        for (int i = pos + 1; i < nums.size(); i++)
//        {
//            if (nums[i] > nums[pos])
//            {
//                if (memo[i] != 0)
//                    ans = max(ans, memo[i]);
//                else
//                    ans = max(ans, dfs(nums, memo, i));
//            }
//        }
//        memo[pos] = ans + 1;
//        return memo[pos];
//    }
//};



//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size();
//        if (n < 2) return n;
//
//        int left = 0, right, ret = 1;
//        for (int i = 0; i < n - 1; i++)
//        {
//            if (nums[i] != nums[i + 1])
//            {
//                right = nums[i + 1] - nums[i];
//                if (left * right <= 0) ret++;
//                left = right;
//            }
//        }
//        return ret;
//    }
//};